#include<vector>
#include<iostream>
using namespace std;

struct SkiplistNode {
public:
    SkiplistNode(int val, int level)
        :_val(val)
    {
        _next.resize(level);
    }
public:
    int _val;
    vector<SkiplistNode*> _next;
};


class Skiplist {
public:
    typedef SkiplistNode Node;
    Skiplist(int maxlevel = 32)
        :_maxLevel(maxlevel)
    {
        srand(time(nullptr));
        _head = new Node(-1, 1);
    }

    bool search(int target) {
        Node* cur = _head;
        int level = _head->_next.size() - 1;
        while (level >= 0) {
            if (cur->_next[level] && cur->_next[level]->_val < target) {
                cur = cur->_next[level];
            }
            else if (!cur->_next[level] || cur->_next[level]->_val > target) {
                --level;
            }
            else {
                return true;
            }
        }
        return false;
    }

    void add(int num) {
        //要先找前一个点
        vector<Node*> prev(_maxLevel, _head);
        Node* cur = _head;
        int level = _head->_next.size() - 1;

        while (level >= 0) {
            if (cur->_next[level] && cur->_next[level]->_val < num) {
                cur = cur->_next[level];
            }
            else if (!cur->_next[level] || cur->_next[level]->_val >= num) {
                prev[level] = cur;
                --level;
            }
        }

        //随机出一个层数
        int n = randLevel();

        //扩_head
        if (n > _head->_next.size()) {
            _head->_next.resize(n, nullptr);
        }

        Node* newnode = new Node(num, n);
        for (int i = 0; i < n; i++) {
            newnode->_next[i] = prev[i]->_next[i];
            prev[i]->_next[i] = newnode;
        }
    }

    void Print() {
        Node* cur = _head;
        int level = _head->_next.size() - 1;
        while (level >= 0) {
            cur = _head;
            while (cur) {
                cout << cur->_val << "->";
                cur = cur->_next[level];
            }
            level--;
            cout << endl;
        }
    }


    bool erase(int num) {
        int level = _head->_next.size() - 1;
        Node* cur = _head;

        vector<Node*> prev(level + 1, _head);
        while (level >= 0) {
            if (cur->_next[level] && cur->_next[level]->_val < num) {
                cur = cur->_next[level];
            }
            else if (!cur->_next[level] || cur->_next[level]->_val >= num) {
                prev[level] = cur;
                --level;
            }
        }

        //判断一下能否找到
        if (!prev[0]->_next[0] || prev[0]->_next[0]->_val != num) {
            return false;
        }
        //链接关系
        Node* del = prev[0]->_next[0];
        for (int i = 0; i < del->_next.size(); i++) {
            //前后关系
            prev[i]->_next[i] = del->_next[i];
        }
        delete del;

        //如果头结点改变了，降低一下高度
        int i = _head->_next.size() - 1;
        while (i >= 0) {
            if (!_head->_next[i])
                --i;
            else
                break;
        }
        _head->_next.resize(i + 1);
        return true;
    }

    int randLevel() {
        int level = 1;
        while (rand() < RAND_MAX * _p && level < _maxLevel) {
            ++level;
        }
        return level;
    }

private:
    int _maxLevel;
    Node* _head;
    double _p = 0.5;//生成下一层的概率
};


int main() {
    Skiplist sl;
    int a[] = { 5,6,9,3,2,1 };
    for (auto e : a) {
        sl.add(e);
    }
    sl.Print();
    return 0;
}